package leetcode.ch3;

public class P32_2 {
    /**
     * 动态规划解决 太难理解
     */


    public int longestValidParentheses(String s) {

        int maxans = 0;
        int dp[] = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')'){
                if (s.charAt(i-1) == '('){
                    dp[i] = (i >=2 ? dp[i-1]:0) +2;
                }else{
                    if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }

                    maxans = Math.max(maxans,dp[i]);
                }
            }
        }


        return maxans;
    }




}
